﻿using BusinessEntities;
using DataAccessLayer;
using Draco.Algorithms;
using Draco.DataStructure;

namespace BusinessLayer
{
    //邻接链表结构
    public class MetroGraph : LocatingPointBLL<MetroNode>
    {

        #region 字段

        private D_LinkList<MetroLine> lineList; //所有线路
        private D_LinkList<MetroNode> transferNodeList; //所有换乘站
        private D_LinkList<MetroNode> nodeList; //所有站点
        private D_EasyHash<MetroLine> lineDict;  //路线表
        private D_LinkList<MetroLink> linkList;  //所有路段

        #endregion

        #region 属性

        public D_LinkList<MetroLine> Lines { get { return lineList; } }
        public D_LinkList<MetroNode> Nodes { get { return nodeList; } }
        public D_EasyHash<MetroLine> LineDict { get { return lineDict; } }
        public D_LinkList<MetroLink> Links { get { return linkList; } }

        #endregion

        #region 初始化

        //构造函数
        public MetroGraph()
        {
            InitGraph();
        }

        private void InitGraph()
        {
            MetroDAL dal = new MetroDAL();

            lineList = new D_LinkList<MetroLine>();
            transferNodeList = new D_LinkList<MetroNode>();
            nodeList = new D_LinkList<MetroNode>();
            lineDict = new D_EasyHash<MetroLine>();
            linkList = new D_LinkList<MetroLink>();


            //初始化站点
            nodeList = dal.GetElements();

            //初始化线路
            foreach (MetroNode node in nodeList)
            {
                foreach (int line in node.Lines)
                {
                    InitLine(line, node);
                }
                if (node.Lines.Count > 1)
                {
                    transferNodeList.Add(node); //保存换乘站
                    foreach (int i in node.Lines)
                    {
                        lineDict[i].AddTransferNode(node);
                    }
                }
            }

            //初始化站点间关系
            foreach (MetroLine line in lineList)
            {
                D_SeqQueue<MetroNode> nodeQueue = new D_SeqQueue<MetroNode>(line.Nodes.Count);
                foreach (MetroNode node in line.Nodes)
                {
                    nodeQueue.Enqueue(node);
                }

                while (nodeQueue.Count > 0)
                {
                    MetroNode curNode = nodeQueue.Dequeue();

                    if (curNode.IsTerminal && curNode.Links.Count > 0) continue;
                    if (curNode.Links.Count >= curNode.Lines.Count * 2) continue;

                    MetroNode nearNode1 = null, nearNode2 = null;
                    int nearSqrDis1 = int.MaxValue, nearSqrDis2 = int.MaxValue;
                    bool hasLink = false;
                    foreach (MetroLink curLink in curNode.Links)
                    {
                        if (curLink.LineID == line.ID)
                        {
                            nearNode1 = curNode.Links[0].To;
                            nearSqrDis1 = D_Vector2D.SqrDistance(curNode.X, curNode.Y, nearNode1.X, nearNode1.Y);
                            hasLink = true;
                        }
                    }
                    D_SeqQueue<MetroNode> tempQueue = new D_SeqQueue<MetroNode>(nodeQueue.Count);
                    while (!tempQueue.IsFull())
                    {
                        MetroNode tempNode = nodeQueue.Dequeue();
                        int tempDis = D_Vector2D.SqrDistance(curNode.X, curNode.Y, tempNode.X, tempNode.Y);
                        if (!hasLink && tempDis < nearSqrDis1 && (nearNode1 == null || D_Vector2D.IsSameQuadrant(curNode.X, curNode.Y, nearNode1.X, nearNode1.Y, tempNode.X, tempNode.Y)))
                        {
                            nearNode1 = tempNode;
                            nearSqrDis1 = tempDis;
                        }
                        else if (tempDis < nearSqrDis2 && !D_Vector2D.IsSameQuadrant(curNode.X, curNode.Y, nearNode1.X, nearNode1.Y, tempNode.X, tempNode.Y))
                        {
                            nearNode2 = tempNode;
                            nearSqrDis2 = tempDis;
                        }
                        tempQueue.Enqueue(tempNode);
                    }
                    nodeQueue = tempQueue;
                    //添加边关系


                    if (nearNode2 == null && !hasLink)
                    {
                        //起始站只加一边关系
                        linkList.Add(curNode.AddMetroLink(new MetroLink(curNode, nearNode1, line.ID)));
                        nearNode1.AddMetroLink(new MetroLink(nearNode1, curNode, line.ID));
                    }
                    else
                    {
                        if (!hasLink) //已经有一边的只需再加一边就可以了
                        {
                            linkList.Add(curNode.AddMetroLink(new MetroLink(curNode, nearNode1, line.ID)));
                            nearNode1.AddMetroLink(new MetroLink(nearNode1, curNode, line.ID));
                        }
                        linkList.Add(curNode.AddMetroLink(new MetroLink(curNode, nearNode2, line.ID)));
                        nearNode2.AddMetroLink(new MetroLink(nearNode2, curNode, line.ID));
                    }
                }
            }
        }

        private void InitLine(int id, MetroNode node)
        {
            if (id > 0)
            {
                if (lineDict.ContainsKey(id))
                {
                    lineDict[id].AddNode(node);
                }
                else
                {
                    MetroLine line = new MetroLine(id);
                    line.AddNode(node);
                    lineList.Add(line);
                    lineDict.Add(id, line);
                }
            }
        }

        #endregion

        #region 查找路径

        /// <summary>
        /// 查找路径
        /// </summary>
        /// <param name="startNode">开始站点</param>
        /// <param name="endNode">结束站点</param>
        /// <param name="option">查找方式</param>
        /// <returns>所查到的路径</returns>
        public MetroPath FindPath(string startNode, string endNode, SeekPathOption option)
        {
            MetroNode[] nodes = StringToNodes(startNode, endNode);
            MetroPath path = new MetroPath();
            switch (option)
            {
                case SeekPathOption.Shortest:
                    path = FindShortestPath(nodes[0], nodes[1]);
                    break;
                case SeekPathOption.Cheapest:
                    path = FindShortestPath(nodes[0], nodes[1]);
                    break;
                case SeekPathOption.LeastTime:
                    path = FindLeastTimePath(nodes[0], nodes[1]);
                    break;
                case SeekPathOption.LeastTransfer:
                    path = FindLeastTransferPath(nodes[0], nodes[1]);

                    break;
            }
            return path;
        }

        private MetroNode[] StringToNodes(params string[] str)
        {
            MetroNode[] nodes = new MetroNode[str.Length];
            foreach (MetroNode node in nodeList)
            {
                for (int i = 0; i < str.Length; i++)
                {
                    if (str[i] == node.Name)
                    {
                        nodes[i] = node;
                    }
                }
            }
            return nodes;
        }

        //寻找最少换乘路径
        private MetroPath FindLeastTransferPath(MetroNode startNode, MetroNode endNode)
        {
            MetroPath path = new MetroPath();

            if (startNode == null || endNode == null) return path;
            if (startNode == endNode) return path;

            //先找直达
            path = FindDirectPath(startNode, endNode);
            if (path.Links.Count > 0) return path;

            //再找一次换乘
            path = FindOneTransferPath(startNode, endNode);
            if (path.Links.Count > 0) return path;

            //再找两次换乘
            path = FindTwoTransferPath(startNode, endNode);
            if (path.Links.Count > 0) return path;

            return path;
        }

        //寻找最短路径
        private MetroPath FindShortestPath(MetroNode startNode, MetroNode endNode)
        {
            MetroPath path = new MetroPath();
            path = FindInTwoTransferPath(startNode, endNode);
            return path;
        }

        //寻找耗时最少路径
        private MetroPath FindLeastTimePath(MetroNode startNode, MetroNode endNode)
        {
            MetroPath path = new MetroPath();
            path = FindInTwoTransferLeastTimePath(startNode, endNode);
            return path;
        }

        //寻找直达路径
        private MetroPath FindDirectPath(MetroNode startNode, MetroNode endNode)
        {
            MetroPath path = new MetroPath();
            int lineID = -1;
            foreach (int i1 in startNode.Lines)
                foreach (int i2 in endNode.Lines)
                    if (i1 == i2)
                        lineID = i1;
            if (lineID == -1) //两站间没有直达路径
            {
                return path;
            }

            if (startNode == endNode) return path; //已经到达

            MetroLine line = lineDict[lineID];

            //深度优先遍历
            D_SeqQueue<MetroNode> nodeQueue = new D_SeqQueue<MetroNode>(line.Nodes.Count);
            MetroNode visitedNode = null; //标识已访问的站点
            foreach (MetroLink startLink in startNode.Links)
            {
                if (startLink.LineID != lineID) continue;

                path.AddLinks(startLink);

                visitedNode = startNode;
                nodeQueue.Clear();
                nodeQueue.Enqueue(startLink.To);

                while (nodeQueue.Count > 0)
                {
                    MetroNode temp = nodeQueue.Dequeue();

                    if (temp == endNode)
                    {
                        //到达目的地
                        return path;
                    }

                    foreach (MetroLink link in temp.Links)
                    {
                        if (link.LineID == lineID && link.To != visitedNode)
                        {
                            visitedNode = temp;
                            nodeQueue.Enqueue(link.To);
                            path.AddLinks(link);
                            break;
                        }
                    }
                }
                path.Clear();
            }

            return path;
        }

        //寻找一次换乘路径
        private MetroPath FindOneTransferPath(MetroNode startNode, MetroNode endNode)
        {
            MetroPath path = new MetroPath();

            foreach (int startLine in startNode.Lines)
            {
                foreach (int endLine in endNode.Lines)
                {
                    foreach (MetroNode tNode in lineDict[startLine].TransferNodes)
                    {
                        if ((tNode.Lines[0] == startLine && tNode.Lines[1] == endLine) ||
                            (tNode.Lines[0] == endLine && tNode.Lines[1] == startLine))
                        {
                            //可以一次换乘到达目的地，而且可能不止一条一次换成就能到达目的地的路
                            MetroPath tempPath = new MetroPath();
                            tempPath = FindDirectPath(startNode, tNode);
                            tempPath.Merge(FindDirectPath(tNode, endNode));
                            if (tempPath.GetDistance() < path.GetDistance())
                            {
                                path = tempPath;
                            }
                        }
                    }
                }
            }
            return path;
        }

        //寻找两次换乘路径
        private MetroPath FindTwoTransferPath(MetroNode startNode, MetroNode endNode)
        {
            MetroPath path = new MetroPath();

            foreach (int endLine in endNode.Lines)
            {
                foreach (MetroNode tNode in lineDict[endLine].TransferNodes)
                {
                    MetroPath tempPath = new MetroPath();
                    tempPath = FindOneTransferPath(startNode, tNode);
                    if (tempPath.Links.Count > 0)
                    {
                        tempPath.Merge(FindDirectPath(tNode, endNode));
                        if (tempPath.GetDistance() < path.GetDistance())
                        {
                            path = tempPath;
                        }
                    }
                }
            }
            return path;
        }

        //寻找一次换乘内最短路径
        private MetroPath FindInOneTransferPath(MetroNode startNode, MetroNode endNode)
        {
            MetroPath path = new MetroPath();

            //先找直达,能直达一定是最近
            path = FindDirectPath(startNode, endNode);
            if (path.Links.Count > 0) return path;

            foreach (int startLine in startNode.Lines)
            {
                foreach (int endLine in endNode.Lines)
                {
                    foreach (MetroNode tNode in lineDict[startLine].TransferNodes)
                    {
                        if ((tNode.Lines[0] == startLine && tNode.Lines[1] == endLine) ||
                            (tNode.Lines[0] == endLine && tNode.Lines[1] == startLine))
                        {
                            //可以一次换乘到达目的地，而且可能不止一条一次换成就能到达目的地的路
                            MetroPath tempPath = new MetroPath();
                            tempPath = FindDirectPath(startNode, tNode);
                            tempPath.Merge(FindDirectPath(tNode, endNode));
                            if (tempPath.GetDistance() < path.GetDistance())
                            {
                                path = tempPath;
                            }
                        }
                    }
                }
            }
            return path;
        }

        //寻找两次换乘内最短路径
        private MetroPath FindInTwoTransferPath(MetroNode startNode, MetroNode endNode)
        {
            MetroPath path = new MetroPath();

            //先找直达,能直达一定是最近
            path = FindDirectPath(startNode, endNode);
            if (path.Links.Count > 0) return path;

            //再找一次换乘最短路径，但一次换乘不一定是最近
            path = FindOneTransferPath(startNode, endNode);

            foreach (int endLine in endNode.Lines)
            {
                foreach (MetroNode tNode in lineDict[endLine].TransferNodes)
                {
                    MetroPath tempPath = new MetroPath();
                    tempPath = FindOneTransferPath(startNode, tNode);
                    if (tempPath.Links.Count > 0)
                    {
                        tempPath.Merge(FindDirectPath(tNode, endNode));
                        if (tempPath.GetDistance() < path.GetDistance())
                        {
                            path = tempPath;
                        }
                    }
                }
            }
            return path;
        }

        //寻找两次换乘内耗时最少路径
        private MetroPath FindInTwoTransferLeastTimePath(MetroNode startNode, MetroNode endNode)
        {
            MetroPath path = new MetroPath();

            //先找直达,能直达一定是耗时最少
            path = FindDirectPath(startNode, endNode);
            if (path.Links.Count > 0) return path;

            //再找一次换乘最短路径，但一次换乘不一定是耗时最短
            path = FindOneTransferPath(startNode, endNode);

            foreach (int endLine in endNode.Lines)
            {
                foreach (MetroNode tNode in lineDict[endLine].TransferNodes)
                {
                    MetroPath tempPath = new MetroPath();
                    tempPath = FindOneTransferPath(startNode, tNode);
                    if (tempPath.Links.Count > 0)
                    {
                        tempPath.Merge(FindDirectPath(tNode, endNode));
                        if (tempPath.GetTime() < path.GetTime())
                        {
                            path = tempPath;
                        }
                    }
                }
            }
            return path;
        }

        #endregion

        #region 查找附近站点

        /// <summary>
        /// 查找指定坐标附近的站点
        /// </summary>
        /// <param name="x">坐标x</param>
        /// <param name="y">坐标y</param>
        /// <param name="errorLevel">允许误差范围</param>
        /// <returns>站点列表</returns>
        public override D_LinkList<MetroNode> GetNearbySites(int x, int y, SeekAdmissibleError errorLevel)
        {
            int hashLen = 8;
            switch (errorLevel)
            {
                case SeekAdmissibleError.Level_1:
                    hashLen = 8;
                    break;
                case SeekAdmissibleError.Level_2:
                    hashLen = 7;
                    break;
                case SeekAdmissibleError.Level_3:
                    hashLen = 6;
                    break;
                case SeekAdmissibleError.Level_4:
                    hashLen = 5;
                    break;
                case SeekAdmissibleError.Level_5:
                    hashLen = 4;
                    break;
                case SeekAdmissibleError.Level_6:
                    hashLen = 3;
                    break;
                case SeekAdmissibleError.Level_7:
                    hashLen = 2;
                    break;
                case SeekAdmissibleError.Level_8:
                    hashLen = 1;
                    break;
            }
            D_GeoHash geo = new D_GeoHash(x, y);
            geo.SetHashLenght(hashLen);
            return GetNearbyMetroNodes(geo.GetGeoHashBase4For9());
        }

        private D_LinkList<MetroNode> GetNearbyMetroNodes(string geohash)
        {
            D_LinkList<MetroNode> nearby = new D_LinkList<MetroNode>();
            foreach (MetroNode node in nodeList)
            {
                if (D_String.PrefixMatching(node.GeoHash, geohash))
                {
                    nearby.Add(node);
                }
            }
            return nearby;
        }

        private D_LinkList<MetroNode> GetNearbyMetroNodes(D_LinkList<string> geohashs)
        {
            D_LinkList<MetroNode> nearby = new D_LinkList<MetroNode>();
            foreach (MetroNode node in nodeList)
            {
                foreach (string geohash in geohashs)
                {
                    if (D_String.PrefixMatching(node.GeoHash, geohash))
                    {
                        nearby.Add(node);
                    }
                }
            }
            return nearby;
        }

        #endregion

        #region 后台操作

        public override MetroNode GetSite(int id)
        {
            foreach (MetroNode node in Nodes)
            {
                if (node.ID == id)
                {
                    return node;
                }
            }
            return null;
        }

        public override void AddSite(MetroNode site)
        {
            //id从数据库获得
            MetroDAL dal = new MetroDAL();
            dal.Insert(site.Name, site.X, site.Y, site.IsTerminal ? 1 : 0, site.Lines[0], (site.Lines.Count > 1) ? site.Lines[1] : -1);

            int id = dal.GetLastInsertID();
            MetroNode temp = new MetroNode(id, site.Name, site.X, site.Y, site.IsTerminal, site.Lines[0], (site.Lines.Count > 1) ? site.Lines[1] : -1);
            Nodes.Add(temp); //为了显示，暂未修改图结构
            //局部修改图

            //添加站点后重新构造整个图
            //InitGraph(); 暂不支持实时更改
        }

        public override void UpdateSite(MetroNode site)
        {

            //局部修改图
            for (int i = 0; i < Nodes.Count; i++)
            {
                if (Nodes[i].ID == site.ID)
                {
                    Nodes[i] = site; //为了显示，暂未修改图结构
                }
            }

            //更新数据库
            MetroDAL dal = new MetroDAL();
            dal.Update(site.ID, site.Name, site.X, site.Y, site.IsTerminal ? 1 : 0, site.Lines[0], (site.Lines.Count > 1) ? site.Lines[1] : -1);

            //重新构造整个图
            //InitGraph();  暂不支持实时更改
        }

        public override void DeleteSite(int id)
        {
            //局部修改图
            int[] array = new int[Nodes.Count];
            for (int i = 0; i < Nodes.Count; i++)
            {
                array[i] = Nodes[i].ID;
            }
            int index = D_Search.BinarySearchIndex(array, id);

            Nodes.RemoveAt(index); //为了显示，暂未修改图结构

            //更新数据库
            MetroDAL dal = new MetroDAL();
            dal.Delete(id);

            //重新构造整个图
            //InitGraph(); 暂不支持实时更改
        }

        /// <summary>
        /// 手动调用更新图结构
        /// </summary>
        public void UpdateGraph()
        {
            InitGraph();
        }

        #endregion

    }

    /// <summary>
    /// 查询路径方式
    /// </summary>
    public enum SeekPathOption
    {
        LeastTransfer,
        Shortest,
        LeastTime,
        Cheapest
    }

}
